package backtrackAlgorithm;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author kunkun
 * @className LeetCode_79
 * @Description 单词搜索
 * @date 2025/3/20 14:26
 */
public class LeetCode_79 {

    @Test
    public void test(){
        char[][] board = new char[][]{{'A','B'},{'C','D'}} ;
        System.out.println(exist(board, "ABDC"));
    }


    public boolean exist(char[][] board, String word) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j]==word.charAt(0)){
                    int[][] flag = new int[board.length][board[i].length];
                    solution_1(0,i,j,flag,word,list,board);
                    if (list.size()>0){
                        return true;
                    }
                }
            }
        }
        return false;
    }



    private void solution_1(int index, int i, int j, int[][] flag, String word, List list, char[][] board) {
        //1. 判断
        if (index>=word.length()){
            list.add(1);
            return;
        }
        if (i<0 || i>=board.length || j<0 || j>=board[0].length){
            return;
        }
        if (flag[i][j]==1){
            return;
        }
        //2. 探索
        if (word.charAt(index)==board[i][j]){
            flag[i][j]=1;
            //2.1 上探索
            solution_1(index+1,i-1,j,flag,word,list,board);
            //2.2 右探索
            solution_1(index+1,i,j+1,flag,word,list,board);
            //2.3 下探索
            solution_1(index+1,i+1,j,flag,word,list,board);
            //2.4 左探索
            solution_1(index+1,i,j-1,flag,word,list,board);
            flag[i][j]=0;
        }
    }
}
